package LC;

import java.util.SortedSet;
import java.util.TreeSet;

/**
 * https://leetcode.com/problems/contains-duplicate-iii/description/
 * Given an array of integers, find out whether there are two distinct indices i and j in the array
 * such that the absolute difference between nums[i] and nums[j]
 * is at most t and the absolute difference between i and j is at most k.
 */
public class LC_220_ContainsDuplicateIII_SortedSet {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 1, 2, 34, 4};
        int k = 5;
        int t = 3;
        System.out.println(Solution.containsNearbyAlmostDuplicate(nums, k, t));
    }

    static class Solution {
        static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (k < 1 || t < 0 || nums == null || nums.length < 2) return false;
            SortedSet<Long> set = new TreeSet<>();
            for (int j = 0; j < nums.length; j++) {
                SortedSet<Long> subSet = set.subSet((long) nums[j] - t, (long) nums[j] + t + 1);
                if (!subSet.isEmpty()) return true;
                if (j >= k) set.remove((long) nums[j - k]);
                set.add((long) nums[j]);
            }
            return false;
        }
    }
}